package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

/***
 * @description: 平衡二叉查找树简称平衡二叉树，亦称 AVL树
 *      1、可以是空树
 *      2、假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且左右子树高度之差的绝对值不超过 1
 * @author : 青石路
 * @date: 2021/12/10 21:36
 */
public class BalancedBinaryTree {

    /**
     * 树形递归
     *      对于任意一个节点 X，它的左子树是平衡二叉树，它的右子树也是平衡二叉树
     *      并且 |左高 - 右高| <= 1
     *
     *      向左树要的信息：1.是否是平衡二叉树，2.高度
     *      向右树要的信息：1.是否是平衡二叉树，2.高度
     *      左树与右树信息结构体一致，那么信息结构体确立：ReturnData
     *
     */

    /**
     * 判断一颗二叉树是否是平衡二叉树
     * @param root
     * @return
     */
    public static boolean isBbt(TreeNode<String> root) {
        return judgeBbt(root).isBalanced;
    }

    /**
     * 信息结构体
     */
    static class ReturnDate {
        boolean isBalanced;
        int height;

        ReturnDate(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static ReturnDate judgeBbt(TreeNode<String> node) {
        if (node == null) {     // base case
            return new ReturnDate(true, 0);
        }
        ReturnDate leftData = judgeBbt(node.left);
        ReturnDate rightData = judgeBbt(node.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced
                && Math.abs(leftData.height - rightData.height) < 2;
        return new ReturnDate(isBalanced, height);
    }
}
